public class _02 {

/*
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-speed-to-arrive-on-time/
*/

    public void main(String[] args) {
//        int a[] = {1, 2, 3, 4, 5, 6, 7};
        int a[] = {1, 3, 100};
        int b = new Solution().minSpeedOnTime(a, 2.01);
        System.out.println(b);
    }

    class Solution {
        public int minSpeedOnTime(int[] dist, double hour) {
            if (dist.length - 1 > hour) {
                return -1;
            }
            int r = 0, l = 1, m;
            for (int t : dist) {
                if (t > r) {
                    r = t;
                }
            }
            r *= 100;
            while (l < r) {
                m = (r + l) >> 1;
                if (check(dist, m, hour)) {
                    r = m;
                } else {
                    l = m + 1;
                }
            }
            return check(dist, l, hour) ? l : -1;
        }

        private boolean check(int[] dist, int m, double hour) {
            double sum = 0;
            for (int i = 0; i < dist.length - 1; i++) {
                sum += (int) Math.ceil(dist[i] * 1.0 / m);
            }
            sum += dist[dist.length - 1] * 1.0 / m;
            return sum <= hour;
        }
    }

}

